#include "rbTree.h"

//左旋（存疑:注意调用的位置与rotate的配合）
//需要确定传进来x的身份
void rbtree_left_rotate(RBRoot* root,Node* x)
{
    //
    Node* y=x->right;

    //
    x->right=y->left;
    if(y->left!=NULL)
    {
        y->left->parent=x;        
    }
    y->parent=x->parent;

    if(x->parent==NULL)
    {
        //如果“x的父亲”是空结点，则将y设为根结点        
        root->node=y;
    }else{
        if(x->parent->left==x)
        {
            x->parent->left=y;
        }else{
            x->parent->right=y;
        }
    }
    y->left=x;
    x->parent=y;
}

//右旋
void rbtree_right_rotate(RBRoot* root, Node* y)
{
    // 设置x是当前节点的左孩子。
    Node* x = y->left;

    // 将 “x的右孩子” 设为 “y的左孩子”；
    // 如果"x的右孩子"不为空的话，将 “y” 设为 “x的右孩子的父亲”
    y->left = x->right;
    if (x->right != NULL)
        x->right->parent = y;

    // 将 “y的父亲” 设为 “x的父亲”
    x->parent = y->parent;

    if (y->parent == NULL)
    {
        //tree = x;            // 如果 “y的父亲” 是空节点，则将x设为根节点
        root->node = x;            // 如果 “y的父亲” 是空节点，则将x设为根节点
    }
    else
    {
        if (y == y->parent->right)
            y->parent->right = x;    // 如果 y是它父节点的右孩子，则将x设为“y的父节点的右孩子”
        else
            y->parent->left = x;    // (y是它父节点的左孩子) 将x设为“x的父节点的左孩子”
    }

    // 将 “y” 设为 “x的右孩子”
    x->right = y;

    // 将 “y的父节点” 设为 “x”
    y->parent = x;
}